In a multiprocessor system where a common resource cannot be used simultaneously by more than one processing unit, access to the resource must be arbitrated among simultaneous requestors.
Arbitration can be achieved by time-division multiplexing whereby each processing unit is allotted a specific time slot during which it can have the exclusive use of the resource. The drawback for this approach, as manifested in a system where processors operate in burst mode, is that time which could otherwise be used by processors needing the resource must also be allotted to idle processors, thus decreasing the utilization of the resource.
In another arbitration method, as described by Tanenbaum, "Computer Networks", Prentice-Hall Publishing Co., 1981, each processor is required to detect the existence of a collision while it is attempting to gain access to the resource. If a collision is detected, the processor must perform a randomization process before a request is retried. Because of the randomization requirement, this method does not guarantee when a processor may gain access to the resource.
Chiarottino et al, U.S. Pat. No. 4,470,110, "System for Distributed Priority Arbitration Among Several Processing Units Competing for Access to a Common Data Channel", issued Sept. 4, 1984, describe an arbitration method whereby each processor is assigned a priority number. During contention time, iterative bit comparisons are made among all the priority numbers forwarded by the requestors. After each bit comparison, a subset of requestors, which have comparatively lower priority numbers at that bit position, is removed until the processor with the highest priority number ultimately gains access to the resource.
Grimes, U.S. Pat. No. 4,463,445, "Circuitry for Allocating Access to a Demand-shared Bus", issued July 31, 1984, describes a similar method in which the priority numbers are modified by parameter bits which reflect some states of the requestors. His method prioritizes requests first by the states and then by the priority numbers of the requestors. A similar method is described in Taub, "Arbitration and Control Acquisition in the Proposed IEEE 896 Future Bus", IEEE MICRO, August 1984, pp. 28-41. These prioritized arbitration methods lack flexibility because selection of a processor to which access is granted is fixed by the assignment of priority numbers.
There is a need for an improved method in which all the requestors are identified in an unbiased manner. Based upon this method, a centralized arbitration system can be implemented in which the selection of a requestor depends purely on an algorithm executed within a host. The advantages of such a system include the following:
1. The host can service a multiplicity of unranked processors with a scheme that can be changed dynamically, depending on the state of the system.
2. The complexity and functional characteristics of the arbitration system can be made to depend on changeable software running within the host.
3. A subset of requestors to whom access to the resource cannot be granted for some operational reasons can be identified and ignored readily by the host.
4. The time and hardware required for processing the arbitration is kept at a minimum.
5. The number of steps required to identify a subset of requestors does not increase exponentially according to the number of processing units needing the resource.